package _17_剑指Offer;


import _17_剑指Offer.datastrcute.TreeNode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class _07_剑指Offer重建二叉树 {

    Map<Integer, Integer> inorderMap = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 构造中序节点值与索引相关的映射
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }

        return buildTree(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode buildTree(int[] preorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        // 递归终止条件
        if (preorder_left > preorder_right) return null;

        // 在preorder中找寻root节点
        int rootIndex = preorder[preorder_left];
        TreeNode root = new TreeNode(rootIndex);

        // 划分索引
        int splitIndex = inorderMap.get(rootIndex);

        int leftCount = splitIndex - inorder_left;

        root.left = buildTree(preorder, preorder_left + 1, preorder_left + leftCount, inorder_left, splitIndex - 1);

        root.right = buildTree(preorder, preorder_left + leftCount + 1, preorder_right, splitIndex + 1, inorder_right);
        return root;
    }


    // 根据二叉树的前序遍历，确定根节点为第一个
    // 根据二叉树中序遍历，确定根节点左边在左子树，右边在右子树
    public TreeNode buildTree1(int[] preorder, int[] inorder) {
        int orderLength = inorder.length;
        if (orderLength == 0) return null;
        int root = preorder[0];
        // 查询位置
        int rootIndex = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (root == inorder[i]) {
                rootIndex = i;
                break;
            }
        }
        TreeNode rootNode = new TreeNode(root);
        // 构建左子树
        rootNode.left = buildTree1(Arrays.copyOfRange(preorder, 1, 1 + rootIndex), Arrays.copyOfRange(inorder, 0, rootIndex));
        // 构造右子树
        rootNode.right = buildTree1(Arrays.copyOfRange(preorder, 1 + rootIndex, orderLength), Arrays.copyOfRange(inorder, rootIndex + 1, orderLength));

        return rootNode;
    }

}
